package leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class _221_MaximalSquare {
    public static void main(String[] args) {
        Solution solution = new _221_MaximalSquare().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 单调栈 同 85 题
    class Solution {
        private int largestSquare(int[] line) {
            Deque<Integer> stack = new LinkedList<>();
            int n = line.length, res = 0;
            int[] newLine = new int[n + 2];
            for (int i = 0; i < n; i++) {
                newLine[i + 1] = line[i];
            }
            for (int i = 0; i < newLine.length; i++) {
                while (!stack.isEmpty() && newLine[i] < newLine[stack.peek()]) {
                    int height = newLine[stack.peek()];
                    stack.pop();
                    int l = stack.peek();
                    int r = i;
                    int edge = Math.min(height, r - l - 1); // 这里是和 85 题的不同之处
                    res = Math.max(res, edge * edge);
                }
                stack.push(i);
            }
            return res;
        }

        public int maximalSquare(char[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            int res = 0;
            int[] line = new int[n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i == 0) {
                        line[j] = matrix[i][j] == '1' ? 1 : 0;
                    } else {
                        line[j] = matrix[i][j] == '1' ? line[j] + 1 : 0;
                    }
                }
                res = Math.max(res, largestSquare(line));
            }
            return res;
        }
    }

    // 官方题解的动态规划
    class Solution2 {
        public int maximalSquare(char[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            int[][] dp = new int[m][n];
            int res = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '1') {
                        if (i == 0 || j == 0) {
                            dp[i][j] = 1;
                        } else {
                            dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                        }
                        res = Math.max(res, dp[i][j]);
                    }
                }
            }
            return res * res;
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}